package es.ull.etsii.aa.metodos;

import java.util.Collections;
import java.util.LinkedList;
import java.util.Random;

import es.ull.etsii.aa.datos.Nodo;
import es.ull.etsii.aa.datos.Problema;
import es.ull.etsii.aa.datos.SolucionTTRP;

public class BL {

	private Problema problema;
	
	public BL (Problema problema) {
		this.problema = problema;
	}
	
	/**
	 * Realiza una busqueda local, tratando de mejorar la solucion provista.
	 * 
	 * @param solucion
	 *            Solucion a tratar de mejorar.
	 * @return Solucion mejorada.
	 */
	public SolucionTTRP busquedaLocal(SolucionTTRP solucion) {
		SolucionTTRP mejor = solucion;

		boolean betterFound;

		do {
			betterFound = false;

			SolucionTTRP aux = exploraVecinos((LinkedList<Nodo>) mejor
					.getTour());

			if (aux.compareTo(mejor) < 0) {
				mejor = aux;
				betterFound = true;
			}

		} while (betterFound);

		return mejor;
	}

	/**
	 * Explora soluciones vecinas y retorna la mejor.
	 * 
	 * @param tour
	 *            Tour que representa una solucion.
	 * @return Mejor solucion vecina.
	 */
	private SolucionTTRP exploraVecinos(LinkedList<Nodo> tour) {
		LinkedList<SolucionTTRP> listaSoluciones = new LinkedList<SolucionTTRP>();

		listaSoluciones.addAll(exploraVecinos1(tour));
		listaSoluciones.addAll(exploraVecinos2(tour));
		listaSoluciones.addAll(exploraVecinos3(tour));

		Collections.sort(listaSoluciones);

		return listaSoluciones.getFirst();
	}

	/**
	 * Exploracion de entornos 1 - Inversion del orden de visita de los nodos.
	 * 
	 * @param tour Nodo a partir del cual explorar vecinos.
	 * @return Lista de soluciones halladas.
	 */
	private LinkedList<SolucionTTRP> exploraVecinos1(LinkedList<Nodo> tour) {
		LinkedList<SolucionTTRP> listaSoluciones = new LinkedList<SolucionTTRP>();
		Random rng = new Random(System.nanoTime());
		RFCS rfcs = new RFCS(problema);

		// Primer metodo - Invertir orden de nodos
		if (problema.getNumeroNodos() >= 3) {
			for (int i = 0; i < problema.getNumeroNodos() / 2; i++) {

				// Indice aleatorio entre el primer nodo y el antepenultimo nodo
				int indice = rng.nextInt(tour.subList(1, tour.size() - 1)
						.size() - 2);

				for (int j = indice; j < indice + 3; j++) {
					LinkedList<Nodo> tourMod = new LinkedList<Nodo>(
							tour.subList(1, tour.size() - 1));
					
					LinkedList<Nodo> tourAux = new LinkedList<Nodo>(tourMod.subList(indice, j));
					Collections.reverse(tourAux);
					
					tourMod.removeAll(tourAux);
					tourMod.addAll(indice, tourAux);
					
					tourMod.addFirst(tour.getFirst());
					tourMod.addLast(tour.getFirst());
					
					listaSoluciones.add(rfcs.evaluar(tourMod));
				}
			}
		}

		return listaSoluciones;
	}

	/**
	 * Exploracion de entornos 2 - Intercambio de nodos.
	 * 
	 * @param tour Nodo a partir del cual explorar vecinos.
	 * @return Lista de soluciones halladas.
	 */
	private LinkedList<SolucionTTRP> exploraVecinos2(LinkedList<Nodo> tour) {
		LinkedList<SolucionTTRP> listaSoluciones = new LinkedList<SolucionTTRP>();
		Random rng = new Random(System.nanoTime());
		RFCS rfcs = new RFCS(problema);

		// Segundo metodo - Intercambiar nodos
		for (int i = 0; i < problema.getNumeroNodos() / 2; i++) {
			LinkedList<Nodo> tourMod = new LinkedList<Nodo>(tour.subList(1,
					tour.size() - 1));

			int indice1 = rng.nextInt(tourMod.size()), indice2;

			do {
				indice2 = rng.nextInt(tourMod.size());
			} while (indice1 == indice2);

			Collections.swap(tourMod, indice1, indice2);

			tourMod.addFirst(tour.getFirst());
			tourMod.addLast(tour.getFirst());

			listaSoluciones.add(rfcs.evaluar(tourMod));
		}

		return listaSoluciones;
	}

	/**
	 * Exploracion de entornos 3 - Intercalacion de nodos.
	 * 
	 * @param tour Nodo a partir del cual explorar vecinos.
	 * @return Lista de soluciones halladas.
	 */
	private LinkedList<SolucionTTRP> exploraVecinos3(LinkedList<Nodo> tour) {
		LinkedList<SolucionTTRP> listaSoluciones = new LinkedList<SolucionTTRP>();
		Random rng = new Random(System.nanoTime());
		RFCS rfcs = new RFCS(problema);

		// Tercer metodo - Intercalar nodos
		if (problema.getNumeroNodos() >= 3) {
			for (int i = 0; i < problema.getNumeroNodos() / 2; i++) {
				LinkedList<Nodo> tourMod = new LinkedList<Nodo>(tour.subList(1,
						tour.size() - 1));

				int indice = rng.nextInt(tourMod.size() - 2);

				tourMod.add(indice + 1, tourMod.remove(indice));

				tourMod.addFirst(tour.getFirst());
				tourMod.addLast(tour.getFirst());

				listaSoluciones.add(rfcs.evaluar(tourMod));
			}
		}

		return listaSoluciones;
	}
}
